// coding: utf-8
// @Author : lryself
// @Date : 2020/10/24 19:16
// @Software: GoLand
// 题目url：https://leetcode-cn.com/problems/video-stitching/solution/shi-pin-pin-jie-by-leetcode-solution/
package main

func main() {
	
}
func videoStitching(clips [][]int, T int) int {
	result_begin := []int{}
	result_end := []int{}
	begin:=0
	end:=T
	for begin<end{
		begin_len:=0
		end_len:=0
		begin_flag:=false
		end_flag:=false
		result_begin=append(result_begin, 0)
		result_end=append(result_end, 0)
		for i,cp :=range clips{
			if cp[0]<=begin{
				begin_flag=true
				if begin_len<(cp[1]-begin){
					begin_len=cp[1]-begin
					result_begin=append(result_begin[:len(result_begin)-1], i)
				}
			}
			if cp[1]>=end{
				end_flag=true
				if end_len<(end-cp[0]){
					end_len=end-cp[0]
					result_end=append(result_end[:len(result_end)-1], i)
				}
			}
			if cp[0]<=begin&&cp[1]>=end{
				return len(RemoveRepByMap(append(result_begin, result_end...)))
			}
		}
		if begin_flag==false{
			result_begin=result_begin[:len(result_begin)-1]
		}
		if end_flag==false{
			result_end=result_end[:len(result_end)-1]
		}
		if begin_flag==false || end_flag == false{
			return -1
		}
		begin=clips[result_begin[len(result_begin)-1]][1]
		end=clips[result_end[len(result_end)-1]][0]
		RemoveRep(clips, result_begin[len(result_begin)-1], result_end[len(result_end)-1])
	}
	return len(RemoveRepByMap(append(result_begin, result_end...)))
}
func RemoveRepByMap(slc []int) []int {
	result := []int{}
	tempMap := map[int]byte{}  // 存放不重复主键
	for _, e := range slc{
		l := len(tempMap)
		tempMap[e] = 0
		if len(tempMap) != l{  // 加入map后，map长度变化，则元素不重复
			result = append(result, e)
		}
	}
	return result
}
func RemoveRep(slc [][]int, x int, y int) [][]int {
	result := [][]int{}
	if x==y{
		if x==len(slc)-1{
			return slc[:x]
		}
		return append(slc[:x], slc[x+1:]...)
	}
	if x==len(slc)-1{
		return append(slc[:y], slc[y+1:]...)
	}
	if y==len(slc)-1{
		return append(slc[:x], slc[x+1:]...)
	}
	if x<y{
		return append(append(append(result, slc[:x]...), slc[x+1:y]...), slc[:y+1]...)
	}
	return append(append(append(result, slc[:y]...), slc[y+1:x]...), slc[:x+1]...)
}
